\section{Heuristics}
In this section we define the three pricing heuristics used in our investigation: Theoretical-Optimal heuristic, Mean heuristic and Human-Interpolation heuristic.  All the three heuristics assume no prior information
about the searcher is available and apply a fixed pricing strategy.
\newline
For pricing heuristic to be considered successful, it needs to improve the average overall revenue.

\subsection{The Theoretical-Optimal Heuristic}
This heuristic assume that all the searchers are fully rational and will apply the optimal search strategy that described by Weitzman \cite{Weitzman1979}.  This heuristic finds the price that will maximize the expected revenue.  The heuristic calculate for each store $s_i$ the reservation value (a threshold) $r_i$ that will satisfy the Equation \ref{eq:rVal}:

\begin{equation} \label{eq:rVal}
c_{s_i}=\int_{x=-\infty}^{r_i} {(r_i-x)f_i(x)dx}.
\end{equation}

Ones the reservation value was calculated for each store, the heuristic calculates for all the stores that their reservation value is smaller than $x+cost$ the probability that their real value is bigger than $x+cost$

Formally, this heuristic sets a price $x$ that will satisfy the Equation \ref{eq:theoreticalOptimal}:

\begin{equation} \label{eq:theoreticalOptimal}
Max_x (x* \prod_{\forall s_i\in r_i(s_i)\leq x+cost}(1-F_{s_i}(x+cost)))
\end{equation}
\newline
The Theoretical-Optimal heuristic is given in Algorithm \ref{alg:optimal}

\begin{algorithm}
\begin{algorithmic}[1]
\caption{Theoretical-Optimal Algorithm}  \label{alg:optimal}
\renewcommand{\algorithmicrequire}{\textbf{Input:}}
\renewcommand{\algorithmicensure}{\textbf{Output:}}

\REQUIRE 
$S$ - Set of stores.\\
$COST$ - The cost of checking my store's price.\\
$X_{Max}$ - Maximum price possible.\\

\ENSURE
$x^*$ - The optimal price.\\

\STATE Initialization: $highest_{revenue}=0$

\FOR {x=1 to $X_{Max}$}

\STATE $prob=1$

\FOR {every $s_i\in S : r_i(s_i)\leq x+cost$}

\STATE $prob=prob*(1-F_{s_i}(x+COST))$ 

\ENDFOR

\IF{$x*prob\geq highest_{revenue}$}
\STATE {$highest_{revenue}=x*prob$}
\STATE {$x^* = x$}
\ENDIF

\ENDFOR

\end{algorithmic}
\end{algorithm}
 
\subsection{The Mean Heuristic}
This heuristic assume that searchers are rationally bounded and likely to follow thumb rules.  We believe that one of the searchers thumb rule when they are facing an opportunity that is characterized by a distribution function is to evaluate the opportunity based on the mean of the distribution.  We designed a mean base search profile based on the thumb rule mentioned above and the mean pricing heuristic which is the optimal pricing heuristic for this search profile.
The mean base searcher has a similar search strategy to the optimal searcher that was described by Weitzman \cite{Weitzman1979}, their stopping rule is similar, they differentiate in the way that they set their reservation value for each opportunity.  While the optimal searcher sets a reservation value for store $s_i$ based on the Equation \ref{eq:rVal}, the mean base searcher sets a reservation value that will satisfy the Equation \ref{eq:Mean} ($Mr_i$ is the mean reservation value for store $s_i$)

\begin{equation} \label{eq:Mean}
Mr_i=c_i+\mu(f_i).
\end{equation}

Ones the reservation value was calculated for each store, the heuristic calculates for all the stores that their reservation value is smaller than $x+cost$ the probability that their real value is bigger than $x+cost$

Formally, this heuristic sets a price $x$ that will satisfy the Equation \ref{eq:meanX}:

\begin{equation} \label{eq:meanX}
Max_x (x* \prod_{\forall s_i\in Mr_i(s_i)\leq x+cost}(1-F_{s_i}(x+cost)))
\end{equation}
\newline
The Mean heuristic is given in Algorithm \ref{alg:meanAlg}

\begin{algorithm}
\begin{algorithmic}[1]
\caption{Mean Algorithm}  \label{alg:meanAlg}
\renewcommand{\algorithmicrequire}{\textbf{Input:}}
\renewcommand{\algorithmicensure}{\textbf{Output:}}

\REQUIRE 
$S$ - Set of stores.\\
$COST$ - The cost of checking my store's price.\\
$X_{Max}$ - Maximum price possible.\\

\ENSURE
$x^*$ - The optimal price.\\

\STATE Initialization: $highest_{revenue}=0$

\FOR {x=1 to $X_{Max}$}

\STATE $prob=1$

\FOR {every $s_i\in S : Mr_i(s_i)\leq x+cost$}

\STATE $prob=prob*(1-F_{s_i}(x+COST))$ 

\ENDFOR

\IF{$x*prob\geq highest_{revenue}$}
\STATE {$highest_{revenue}=x*prob$}
\STATE {$x^* = x$}
\ENDIF

\ENDFOR

\end{algorithmic}
\end{algorithm}

\subsection{The Human-Interpolation Heuristic}
This heuristic assume that searchers are rationally bounded and likely to follow thumb rules.  We believe that one of the searchers thumb rule when they are facing an opportunity that is characterized by a distribution function is to evaluate the opportunity based on interpolation between the cost of checking the real value of the opportunity and a likeliness of a value (probability).  We designed a human-interpolation search profile based on the thumb rule mentioned above and the human-interpolation pricing heuristic which is the optimal pricing heuristic for this search profile.
The human-interpolation searcher sets a reservation value for a certain opportunity dynamically, every time the searcher checks an opportunity the reservation value of the other opportunities and the stopping threshold is changing. A reservation value of an opportunity is a direct interpolation between the opportunity's cost and the probability that the real value of the opportunity will be smaller than the minimal real value that was found up until this point.  The human-interpolation searcher sets a reservation value $Int_{r_i}$ to store $s_i$ that will satisfy Equation \ref{eq:HInter}.

\begin{equation} \label{eq:HInter}
Int_{r_i}(s_i)= \frac{MaxCost-c_i}{MaxCost}*\alpha + F(minRealValue)*(1-\alpha)
\end{equation}

In Equation \ref{eq:HInter} the $MaxCost$ variable is the cost of the opportunity with the highest cost, the $minRealValue$ variable is the minimal real value that was found so far and $\alpha$ is a parameter between 0 to 1 that represent the weight that people give to cost as opposed to probability (We will elaborate on this parameter in Section  ).[avshalom:needs a reference on chapter of alpha]
The stopping rule of the human-interpolation searcher is if the reservation value of the next opportunity in the sequence $Int_{r_i}(s_i)$ is smaller than $1-\alpha$.

The Human-Interpolation heuristic checks for each price $x$ the probability that all the opportunities that their reservation value($Int_{r_i}(s_i)$) is smaller than $1-\alpha$ is bigger than $x+cost$ and multiply this probabilities by $x$.  
Formally, this heuristic sets a price $x$ that will satisfy the Equation \ref{eq:InterX}:

\begin{equation} \label{eq:InterX}
Max_x (x* \prod_{\forall s_i\in Int_{r_i}(s_i)\leq 1-\alpha}(1-F_{s_i}(x+cost)))
\end{equation}
\newline

The Human-Interpolation heuristic is given in Algorithm \ref{alg:InterpolationAlg}

\begin{algorithm}
\begin{algorithmic}[1]
\caption{Human-Interpolation Algorithm}  \label{alg:InterpolationAlg}
\renewcommand{\algorithmicrequire}{\textbf{Input:}}
\renewcommand{\algorithmicensure}{\textbf{Output:}}

\REQUIRE 
$S$ - Set of stores.\\
$COST$ - The cost of checking my store's price.\\
$X_{Max}$ - Maximum price possible.\\
$\alpha$ - Threshold.\\

\ENSURE
$x^*$ - The optimal price.\\

\STATE Initialization: $highest_{revenue}=0$

\FOR {x=1 to $X_{Max}$}

\STATE $prob=1$
\STATE calculate $Int_{r_i}(s_i)$ where $minRealValue=x$

\FOR {every $s_i\in S : Int_{r_i}(s_i)\leq 1-\alpha$}

\STATE $prob=prob*(1-F_{s_i}(x+COST))$ 

\ENDFOR

\IF{$x*prob\geq highest_{revenue}$}
\STATE {$highest_{revenue}=x*prob$}
\STATE {$x^* = x$}
\ENDIF

\ENDFOR

\end{algorithmic}
\end{algorithm}

\section{Evaluation}
\label{sec:Evaluation}
The domain that was chosen in-order to test our hypothesis was the "costly search problem" which can be mapped to the general economic search problem discussed in this work.  The problem considers choosing a store to buy commodity from among a set of homogeneous ones (stores).  The stores differ in the price that they offer the commodity.  Only the distribution of each store's price is known.  To reveal the actual price of a store, it must be queried, an action that cost a certain fee.  Only a store that was queried for it real price can be chosen to buy the commodity from.  The goal is to find the querying strategy that minimizes the overall querying fees and the actual price that the commodity is being sold for.  The mapping of this problem to the sequential search problem (in its cost minimization variant) is straight forward: each store represent an opportunity where its price is the true value and the querying fee is the cost of obtaining the value of that opportunity.

\section{Results And Analysis}
In this research we used programed agents and people to test our heuristics and we compared the results that the programmed agents achieved on the heuristics with the results that people achieved on the heuristics.
The test set used for evaluation (both for programed agents and people) consist "costly search problems", each problem consist of 8 stores.  the querying cost fees (a.k.a parking fees) for each store  was uniformly drawn from the range (1,10).  A multi-rectangular distribution function consist 4 bars(each bar length 25) in the range (0,100) was uniformed normalized generated for each store to describe the probability for the real price that this store sell the commodity.  The real price of a store was drawn from the stores distribution.  Figure \ref{fig:storeExample} depict an example of a store. 
\begin{figure}
	\centering
		\includegraphics[scale=0.3]{store.jpg}
		%\vspace{-10pt}
		\caption{Example of store's distribution}
	\label{fig:storeExample}
	%\vspace{-10pt}
\end{figure}

\subsection{Agents Results}
Thirty one agents, each designed by a different student, were used to test our hypothesis.  Each agent was tested on 15000 "costly search problem"(as described in Section \ref{sec:Evaluation}).  The 1500 problems were actually 5000 problems where the eighth store's price was calculated ones according to the Theoretical-Optimal heuristic, ones according to the Mean heuristic and ones according to the Human-Interpolation heuristic.
\newline
Figure \ref{fig:agents} depicts the average profit of each heuristic over 31 agents.  In average the heuristic that had the best performance over the 31 agents was the Mean heuristic and the heuristic that acted poorly was the Theoretical-Optimal heuristic.  Figure \ref{fig:agentsAverage} depicts the difference of performance between the Theoretical-Optimal heuristic and Mean heuristic, it shows us that even agents that people design are not fully rational and when we design an algorithm that will work with agents we need to take under consideration that people and agents that they design are rationally bounded.

\begin{figure}
	\centering
		\includegraphics[scale=0.3]{agents.pdf}
		%\vspace{-10pt}
		\caption{Three heuristics profit over 31 agents}
	\label{fig:agents}
	%\vspace{-10pt}
\end{figure}

\begin{figure}
	\centering
		\includegraphics[scale=0.3]{agentsAverage.pdf}
		%\vspace{-10pt}
		\caption{Three heuristics average profit over 31 agents}
	\label{fig:agentsAverage}
	%\vspace{-10pt}
\end{figure}


\subsection{People Results}
150 different people participated on our experiment. Each person was tested on 10 "costly search problem"(as described in Section \ref{sec:Evaluation}).  The 10 problems where randomly pooled from a set of 100 problems that their eighth store's price was calculated ones according to the Theoretical-Optimal heuristic, or a set of 100 problems that their eighth store's price was calculated ones according to the Mean heuristic, or a set of 100 problems that their eighth store's price was calculated ones according to the Human-Interpolation heuristic.
\newline
As can be depict from Figure \ref{fig:} The Mean heuristic that achieved the best performance when it was applied to programed agent is not the best heuristic when it was tested on people.  The comparison between the Mean heuristic and the Human-Interpolation heuristic proves our hypothesis that in some scenarios people's decision making is different than the strategies that they design for their agents.
While in the "costly search problem" domain agents designer may use statistic methods to evaluate an opportunity such as calculating the mean or the variance of a distribution, when people face this kind of problems they avoid using this statistical methods because they are computational bounded.  When we design an algorithm, it is important to know if this algorithm will be applied on people or on programmed agent, some algorithms that are very efficient with agents may be not so efficient when we will apply then on people. 